package leetcode_500;

import java.util.Map;
import java.util.TreeMap;

import helpclass.Interval;

/**
 * FindRightInterval_436
 * 2018年8月17日 下午2:44:21
 * @author 周杨
 * describe :
 *
 */
/**
 * FindRightInterval_436
 * 2018年8月17日 下午3:12:37 找起点最小的右区间
 * @author 周杨
 * describe :用treemap  AC 31%
 *
 */
public class FindRightInterval_436 {
	 /**
	 * 2018年8月17日 下午2:45:49
	 * @author 周杨
	 * describe :题目看错了 用的动态规划 用两个数组记录当前左和右遍历的最小合法距离  但是题目要求
	 * 的最小是 合法的最小起点 而不是相隔距离 
	 */
	public int[] findRightInterval1(Interval[] intervals) {
		    if(intervals.length==0)
		    	return new int[]{};
		    int [] left=new int[intervals.length];
		    int [] right=new int[intervals.length];
		    left[0]=-1;
		    right[intervals.length-1]=-1;
	        for(int i=1;i<intervals.length;++i){//仅看左边
	        	int j=i-1;
	        	while(j>=0){
	        		if(intervals[j].start>=intervals[i].end){
	        			left[i]=i-j;
	        			break;
	        		}
	        		else{
	        			if(left[j]==-1){
	        				left[i]=-1;
	        				break;
	        			}
	        			else
	        				j=j-left[j];
	        		}
	        	}
	        }
	        for(int i=intervals.length-2;i>=0;--i){
	        	int j=i+1;
	        	while(j<intervals.length){
	        		if(intervals[j].start>=intervals[i].end){
	        			right[i]=j-i;
	        			break;
	        		}
	        		else{
	        			if(right[j]==-1){
	        				right[i]=-1;
	        				break;
	        			}
	        			else
	        				j=j+right[j];
	        		}
	        	}
	        }
	        for(int i=0;i<intervals.length;++i){
	        	if(left[i]>-1&&right[i]>-1){
	        		left[i]=left[i]>right[i]?i+right[i]:i-left[i];
	        	}
	        	else if(left[i]>-1)
	        		left[i]=i-left[i];
	        	else if(right[i]>-1)
	        		left[i]=i+right[i];
	        }
	        return left;
	 }
	
	/**
	 * 2018年8月17日 下午3:10:40
	 * @author 周杨
	 * describe :利用treemap 每次找最近符合的start
	 */
	public int[] findRightInterval(Interval[] intervals) {
        int[] result = new int[intervals.length];
        
        TreeMap<Integer, Integer> treemap = new TreeMap<>();
        
        for(int i = 0; i < intervals.length; i++) {
            treemap.put(intervals[i].start, i);
        }
        
        for(int i = 0; i < intervals.length; i++) {
            Map.Entry<Integer, Integer> item = treemap.ceilingEntry(intervals[i].end);
            result[i] = (item == null) ? -1 : item.getValue();
        }
        
        return result;
    }
}
